#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int minJumps(vector<int>& arr) {
        if(arr.size() == 1)return 0;
        map<int, set<int>> mp; //存与每个数字相等的其他数字的下标
        vector<int> res(arr.size(), -1); //存到达每个位置的最小步数 初始化-1
        queue<int>q, p;

        //初始化
        for(int i = 0; i < arr.size(); i++){
            if(!mp.count(arr[i])){
                mp[arr[i]] = set<int>();
            }
            mp[arr[i]].insert(i);
        }

        q.push(0);
        res[0] = 0;
        int temp_pos;
        while(!q.empty()){
            while(!q.empty()){
                p.push(q.front());
                q.pop();
            }
            while(!p.empty()){
                temp_pos = p.front();
                p.pop();
                if(temp_pos > 0 && res[temp_pos - 1] == -1){
                    res[temp_pos - 1] = res[temp_pos] + 1;
                    q.push(temp_pos - 1);
                }
                if(temp_pos < res.size() - 1 && res[temp_pos + 1] == -1){
                    res[temp_pos + 1] = res[temp_pos] + 1;
                    q.push(temp_pos + 1);
                }
                if(res[res.size() - 1] != -1)return res[res.size() - 1];
                for(auto it : mp[arr[temp_pos]]){
                    if(res[it] == -1){
                        res[it] = res[temp_pos] + 1;
                        q.push(it);
                    }
                    if(res[res.size() - 1] != -1)return res[res.size() - 1];
                }
                mp[arr[temp_pos]].clear();// 关键剪枝
            }
        }
        return res[res.size() - 1];
    }
};

/**
 * @brief 2022.2.22
 * 记忆化bfs 
 * 剪枝之前会超时，因为遍历了过多无效的路径。
 */